import java.lang.reflect.Array;
import java.util.Random;


public class Sort {
	
	/**
	 * Implement insertion sort.
	 * 
	 * It should be:
	 *  inplace
	 *  stable
	 *  
	 * Have a worst case running time of:
	 *  O(n^2)
	 *  
	 * And a best case running time of:
	 *  O(n)
	 * 
	 * @param arr
	 */
	public static <T extends Comparable<T>> void insertionsort(T[] arr) {
		
		for (int i = 0; i < arr.length; i++){
			T data = arr[i];
			int j = i - 1;
			while (j >= 0 && arr[j].compareTo(data) > 0){
				arr[j + 1] = arr[j];
				j = j - 1;
			}
			arr[j + 1] = data;
		}
	}
	
	/**
	 * Implement quick sort. 
	 * 
	 * Use the provided random object to select your pivots.
	 * For example if you need a pivot between a (inclusive)
	 * and b (exclusive) where b > a, use the following code:
	 * 
	 * int pivotIndex = r.nextInt(b - a) + a;
	 * 
	 * It should be:
	 *  inplace
	 *  
	 * Have a worst case running time of:
	 *  O(n^2)
	 *  
	 * And a best case running time of:
	 *  O(n log n)
	 * 
	 * @param arr
	 */
	public static <T extends Comparable<T>> void quicksort(T[] arr, Random r) {
		recursiveQuicksort(arr, r, 0, arr.length - 1);
	}
	
	public static <T extends Comparable<T>> void recursiveQuicksort(T[] arr, Random r, int min, int max){
		if (min >= max){
			return;
		}
		
		int pivot = r.nextInt(max - min) + min;
		int mid = partition(arr, min, max, pivot);
		
		recursiveQuicksort(arr, r, min, mid - 1);
		recursiveQuicksort(arr, r, mid, max);
	}
	
	public static <T extends Comparable<T>> int partition(T[] arr, int min, int max, int pivot){
		T pivotValue = arr[pivot];
		
		while (min <= max){
			while ( arr[min].compareTo(pivotValue) < 0){
				min += 1;
			}
			while (arr[max].compareTo(pivotValue) > 0){
				max -= 1;
			}
			
			if (min <= max){
				//swap min and max
				T first = arr[min];
				T second = arr[max];
				arr[max] = first;
				arr[min] = second;
				min += 1;
				max -= 1;
			}
		}
		return min;
	}

	
	/**
	 * Implement merge sort.
	 * 
	 * It should be:
	 *  stable
	 *  
	 * Have a worst case running time of:
	 *  O(n log n)
	 *  
	 * And a best case running time of:
	 *  O(n log n)
	 *  
	 * @param arr
	 * @return
	 */
	public static <T extends Comparable<T>> T[] mergesort(T[] arr) {
		if (arr.length == 1){
			return arr;
		}
		
		T[] left = (T[]) new Comparable<?>[arr.length / 2];
		T[] right = (T[]) new Comparable<?>[arr.length - left.length];
		
		for (int i = 0; i < left.length; i++){
			left[i] = arr[i];
		}
		
		for (int i = 0; i < right.length; i++){
			right[i] = arr[left.length + i];
		}
		
		return merge(mergesort(left), mergesort(right), arr.clone());
			
	}
		
	public static <T extends Comparable<T>> T[] merge(T[] left, T[] right, T[] merged){
		int rI = 0;
		int lI = 0;
		int mI = 0;
		
		while (lI < left.length && rI < right.length){
			if (left[lI].compareTo(right[rI]) < 0){
				merged[mI] = left[lI];
				lI += 1;
			}
			
			else{
				merged[mI] = right[rI];
				rI += 1;
			}
			
			mI += 1;
		}
		
		if (lI >= left.length){
			for (int i = rI; i < right.length; i++){
				merged[mI] = right[i];
				mI += 1;
			}
		}
		
		else if (rI >= right.length){
			for (int i = lI; i < left.length; i++){
				merged[mI] = left[i];
				mI += 1;
			}
		}
		
		return merged;
		
	}
	
	
	/**
	 * Implement radix sort
	 * 
	 * Hint: You can use Integer.toString to get a string
	 * of the digits. Don't forget to account for negative
	 * integers, they will have a '-' at the front of the
	 * string.
	 * 
	 * It should be:
	 *  stable
	 *  
	 * Have a worst case running time of:
	 *  O(kn)
	 *  
	 * And a best case running time of:
	 *  O(kn)
	 * 
	 * @param arr
	 * @return
	 */
	public static int[] radixsort(int[] arr) {
		arr = arr.clone();
        final int kBuckets = 18;
        
        int buckets[][] = new int[kBuckets][10];
        for (int i = 0; i < kBuckets; i++) {
                buckets[i][0] = 1;
        }
        
        int digits = maxNumberOfDigits(arr);
        int divisor = 1;
        
        for (int i = 0; i < digits; i++) {
                for (int j : arr) {
                        int normal = ((j / divisor) % 10) + 9;
                        buckets[normal] = add(j, buckets[normal]);
                }
                
                int index = 0;
                for (int j = 0; j < kBuckets; j++) {
                        int[] bucket = buckets[j];
                        
                        for (int k = 1; k < bucket[0]; k++) {
                                arr[index++] = bucket[k];
                        }
                        buckets[j][0] = 1;
                }
                
                divisor *= 10;
        }
        
        return arr;
	}
	
	public static int maxNumberOfDigits(int[] arr) {
	        int maxDigits = Integer.MIN_VALUE;
	        for (int i : arr) {
	                int length = (int)(Math.log10(i) + 1);
	                if (length > maxDigits) {
	                	maxDigits = length;
	                }
	        }
	        return maxDigits;
	}
	
	public static int[] add(int integer, int[] bucket) {
	        int size = bucket[0];
	        if (size >= bucket.length) {
	                int newSize = 2 * bucket.length + 1;
	                int[] oldBucket = bucket;
	                int[] newBucket = new int[newSize];
	                int i = 0;
	                
	                for (int j = 0; j < oldBucket.length; j++) {
	                        int entry = oldBucket[j];
	                        newBucket[i] = entry;
	                        i++;
	                }
	        }
	        bucket[size] = integer;
	        size += 1;
	        bucket[0] = size;
	        return bucket;
	}
}